package com.jacklei;


public class main {
    public static void main(String[] args) {
        String babad = longestPalindrome("babad");
        System.out.println(babad);
    }
    public static String longestPalindrome(String s) {
        char[] T = getTranChar(s);
        return getLen(T);
    }
    public static char[]  getTranChar(String s) {
        char[] chars = s.toCharArray();
        char[] T = new char[chars.length * 2 +1];
        for(int i = 0; i < T.length; i++){
            T[i] = i % 2 == 0 ? '#' : chars[i/2];
        }
        return T ;
    }
    private static String getLen(char[] t) {
        int maxIndex = 0;
        int[] len = new int[t.length];
        len[0] = 1;
        for (int i = 1; i < t.length; i++) {
            //超过最右端的距离R(暴力枚举);
            int maxLen = len[maxIndex];
            if( maxLen <= i - maxIndex){
                int j = 0;
                while (i+j < t.length && i-j >=0 && t[i-j] == t[i+j]){
                    len[i]++;
                    j++;
                }
                maxIndex = len[i] >= len[maxIndex] ? i : maxIndex;
            }else {
                int j = maxIndex - (i - maxIndex);
                //如果 i 的对称 j 回文串完全在 len[maxIndex] 的 内部  -----> len[i] = len[j]
                int lLength= (j - (maxIndex - maxLen));//对称j的回文串的长度R

                if(len[j] < lLength){
                    len[i] = len[j];
                }else if (len[j] > (j - (maxIndex - maxLen))){
                    //如果 i 的对称 j 回文串范围超过 len[maxIndex] 的 内部 -----> len[i] = j - (maxIndex - len[maxIndex])
                    len[i] = j - (maxIndex-maxLen);
                }else {
                    //如果 i 的对称 j 回文串范围恰好在 len[maxIndex] 的 边界 -----> 超出部分继续尝试

                    int k = j - (maxIndex - maxLen);
                    len[i] = lLength;
                    while (i+k < t.length && i-k >=0 && t[i+k] == t[i-k]){
                        len[i]++;
                        k++;
                    }
                    maxIndex = len[i] >= len[maxIndex] ? i : maxIndex;
                }

            }

        }
        int k = maxIndex - len[maxIndex]+2;
        char[] result = new char[((len [maxIndex])*2-1)/2];
        for(int i = 0; i < result.length; i++){
            result[i] =t[k];
            k++;
            k++;
        }
        return String.copyValueOf(result);
    }
}
